/*
2021-7-14
https://www.acwing.com/problem/content/736/ 
*/

#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

int f[10005];
struct strone
{
    int s,v,l;
    bool operator < (const strone & w) const
    {
        return s*w.l<w.s*l;
    }
}a[10005];

int main()
{
    int T;
    cin>>T;
    for(int c=1;c<=T;c++)
    {
        int n;
        cin>>n;
        int m=0;
        for(int i=0;i<n;i++)
        {
            int s,v,l;
            cin>>s>>v>>l;
            a[i]={s,v,l};
            m+=s;
        }
        memset(f,-0x3f,sizeof f);
        f[0]=0;
        sort(a,a+n);
        
        for(int i=0;i<n;i++)
        {
            int s=a[i].s,v=a[i].v,l=a[i].l;
            for(int j=m;j>=s;j--)
                f[j]=max(f[j],f[j-s]+v-l*(j-s));
        }
        int res=0;
        for(int i=0;i<=m;i++) res=max(res,f[i]);
        printf("Case #%d: %d\n",c,res);
    }
    return 0;
}

